#ifndef _CHAINING_H_
#define _CHAINING_H_

#include <vector>
#include <list>
#include <utility>
#include <iterator>

using std::vector;
using std::list;
using std::pair;

namespace genhash
{

template <class Config_>
class Chaining
{

public:
	typedef Config_ Config;
	
	typedef typename Config::KeyType key_type;
	typedef typename Config::DataType data_type;
	typedef pair<key_type, data_type> value_type;

	typedef typename Config::HashFn hasher;

	typedef list<size_t> Bucket;
	typedef vector<Bucket> BucketVector;
   	typedef vector<value_type> DataVector;

	typedef typename DataVector::iterator iterator;

public:

	Chaining()
	: buckets(Config::max_size)
	{
		data.reserve(Config::max_size);
	}

	~Chaining()
	{
	}


	iterator begin()
	{
		return data.begin();
	}

	iterator end()
	{
		return data.end();
	}

	size_t size() const
	{
		return data.size();
	}

	size_t max_size() const
	{
		return Config::max_size;
	}

	bool empty() const
	{
		return data.empty();
	}


	/**
	 * insert
	 */
	pair<iterator, bool> insert(const value_type& x) 
	{ 
		size_t pos = hash_mod(x.first);
		Bucket& bucket = buckets[pos];
		for(Bucket::iterator it = bucket.begin(); it != bucket.end(); ++it)
		{
			size_t idx = *it;
			if(data[idx].first == x.first)
			{
				return make_pair(data.begin() + idx, false);
			}
		}
	    bucket.push_back(data.size());
		data.push_back(x);
		return make_pair(data.begin() + data.size() - 1, true);
	}

	/**
	 * find
	 */	
	iterator find(const key_type& k)
	{
		size_t pos = hash_mod(k);
		Bucket& bucket = buckets[pos];
		for(Bucket::iterator it = bucket.begin(); it != bucket.end(); ++it)
		{
			size_t idx = *it;
			if(data[idx].first == k)
			{
				return data.begin() + idx;
			}
		}
		return data.end();
	}


private:

	/**
	 * hash and mod by the size
	 */
	size_t hash_mod(const key_type& k)
	{
		return hash(k);
	}

	BucketVector buckets;

	DataVector data;

	hasher hash;
};

}

#endif // _CHAINING_H_
